#include <string>
#include <iostream>

#include "bst.h"
using namespace std;
void BSTree::remove(const string& word)
{
    cout << "BSTree::remove has been not implemented yet!" << endl;
}

//Non-Recursive Version
void BSTree::add(const string& word)
{
    if(0 == _head){
        _head = new Tnode();
        _head->word = word;
        _head->count = 1;
        _head->left = _head->right = 0;
    }else{
        Tnode* pnode = _head;
        for(;;){
            int ret = word.compare(pnode->word);
            if(ret == 0){
                ++(pnode->count);
                return;
            }
            else{
                Tnode** p = (ret > 0) ? &pnode->right:&pnode->left;
                if(*p == 0){
                    Tnode* newp = new Tnode();
                    newp->word = word;
                    newp->count = 1;
                    newp->left = newp->right = 0;
                    *p = newp;
                    return;
                }else{
                    pnode = *p;
                }
            }
        }        
    }
}
BSTree::BSTree(Tnode* head):_head(head)
{
}
BSTree::BSTree():_head(0)
{
}
BSTree::~BSTree()
{
    DeleteNode(_head);
    
}
void BSTree::print()
{
    PrintNode(_head);
}
void BSTree::DeleteNode(Tnode* node)
{
    if(node == 0){
        return;
    }
    else{
        DeleteNode(node->left);
        DeleteNode(node->right);
        delete node;
    }
}
void BSTree::PrintNode(Tnode* node)
{
    if(node == 0){
        return;
    }
    else{
        PrintNode(node->left);
        cout << node->word << node->count << endl;
        PrintNode(node->right);
    }
}
